package Hot100;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2021-12-25 13:05
 */
public class sortColors75 {

    /**75. 颜色分类
     * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     * 1、排序，排序后即为结果
     * 2、用数组记录个元素出现的次数，然后重构数组
     * 3、双指针：
     * */
    public void sortColors1(int[] nums) {
        Arrays.sort(nums);
    }

    public void sortColors(int[] nums) {
        int n=nums.length;
        int p0=0,p1=0;
        for (int i = 0; i < n; i++) {
            if (nums[i]==1){
                int temp=nums[i];
                nums[i]=nums[p1];
                nums[p1]=temp;
                p1++;
            }else if (nums[i]==0){
                int temp=nums[i];
                nums[i]=nums[p0];
                nums[p0]=temp;
                if (p0<p1){
                    //当 p_0 < p_1时，我们已经将一些 1 连续地放在头部，此时一定会把一个 1 交换出去，导致答案错误。
                    // 需要再将 nums[i] 与 nums[p1] 进行交换，其中 i 是当前遍历到的位置，在进行了第一次交换后nums[i] 的值为 1，我们需要将这个 1 放到「头部」的末端。
                    temp=nums[i];
                    nums[i]=nums[p1];
                    nums[p1]=temp;
                }
                p0++;p1++;
            }
        }
    }
}
